package com.sx.sx1.lintcode.day717;

//力扣327  lC 1293
public class LC1293 {
    static class Solution {
        /**
         * @param nums: a list of integers
         * @param lower: a integer
         * @param upper: a integer
         * @return: return a integer
         */
        public int countRangeSum(int[] nums, int lower, int upper) {
            //前缀和+双指针
            int n = nums.length;
            int[] sum = new int[n+1];
            for (int i = 0; i <n ; i++) {
                sum[i+1] = sum[i]+ nums[i];
            }

            int[] ans = {0};
            guibing(sum,lower,upper,ans);
            return ans[0];
        }

        //归并排序
        public void guibing(int[] sum,int low,int high,int[] ans){
            int n = sum.length;
            int step =1;
            while (step<n) {
                int left =0;
                while (left< n) {
                    int m = left+step-1; //左组结束位置
                    if(m > n) break;
                    int R = Math.min(m+step,n-1); //右组结束位置
                    merge(sum,left,m,R,ans,low,high);
                    left=R+1; //下一组继续
                }
                if(step > n/2) break;
                step*=2;
            }
        }

        public void merge(int[] sum,int l,int m,int r,int[] ans,int low,int hign){
            /*
            下面这行很重要：  if(l==r) return;
             System.out.println(obj.countRangeSum(new int[]{2147483647,-2147483648,-1,0},-1,0));
                这个才能通过
             */
            if(l==r) return;
            //在合并数组前统计2个升序数组满足的角标对
            int i1=l;
            int l1 = m+1;
            int r1 = m+1;
            while (i1<=m){
                //移动左指针找出满足区间的最小角标
                while (l1<=r && sum[l1]-sum[i1] <low){
                    l1++;
                }
                //移动右指针找出满足区间的最大角标+1
                while (r1<=r && sum[r1]-sum[i1] <=hign){
                    r1++;
                }

                ans[0]+= r1-l1;
                i1++;
            }

            int[] help = new int[r-l+1];
            int i=0;
            int p1 = l;
            int p2 = m+1;
            while (p1<=m && p2<=r){
                if(sum[p1]<=sum[p2]){
                    help[i++] = sum[p1++];
                }else{
                    help[i++] = sum[p2++];
                }
            }

            while (p1<=m){
                help[i++] = sum[p1++];
            }

            while (p2<=r){
                help[i++] = sum[p2++];
            }

            for (int j = 0; j <help.length ; j++) {
                sum[l+j] =help[j];
            }
        }
    }


    public static void main(String[] args) {
        int[] arr1 = {-2,5,-1};
        int[] arr2 = {-0,-3,-3,1,1,2};
        Solution obj = new Solution();
        //System.out.println(obj.countRangeSum(arr1,-2,2));
       //System.out.println(obj.countRangeSum(arr2,3,5));
        System.out.println(obj.countRangeSum(new int[]{2147483647,-2147483648,-1,0},-1,0));
    }
}


/*

[5,-23,-5,-1,-21,13,15,7,18,4,7,26,29,-7,-28,11,-20,-29,19,22,15,25,17,-13,11,-15,19,-8,3,12,-1,2,-1,-21,-10,-7,14,-12,-14,-8,-1,-30,19,-27,16,2,-15,23,6,14,23,2,-4,4,-9,-8,10,20,-29,29]
-19
10
输出数据
50

期望答案
362



[-2,0,-2,-3,2,2,1,-3,4]
4
11
输出数据
4

期望答案
5

提示
Review your code and make sure your algorithm is correct. Wrong answer usually caused by typos if your algorithm is correct.
评测过程会影响此处显示的输出结果，但不会影响代码本身输出的值。
控制台

327.区间和的个数
给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

说明:
最直观的算法复杂度是 O(N²) ，请在此基础上优化你的算法。

示例:

输入: nums = [-2,5,-1], lower = -2, upper = 2,
输出: 3
解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。
1
2
3
一句话：
给一个数组和一个区间，求数组中有多少个【连续的元素之和】在这个区间内。

解题思路：
第一时间想到暴力法，但是题目明确说明不能使用暴力法，暴力法的时间复杂度为O(N²)。暴力法代码在文章最后。刷题最重要是先想到解决方案，然后考虑优化～

此解法参考官方解答：前缀和 + 归并排序

根据数组算出前缀和数组 preSums，问题等价求 preSum[j] - preSum[i] 在区间内的个数
将 preSums 平分为2段 lefts 和 rights，求得 rights[j] - lefts[i] 在区间内的个数。然后按照此方法继续分解lefts 和 rights，直到分解不动。累加每一次的结果就是最后的结果
假设 lefts 和 rights 都是有序的，问题变得简单很多。定义3个指针 i ，l，r。i 指向 lefts[0]，l 和 r 指向 rights[0]。移动 l 找出第一个 rights[l] - lefts[i] 在区间内的点，再移动 r 找出最后一个 rights[r] - lefts[i] 在区间内的点，「r - l + 1 」即为本次的个数。然后移动 i 指向lefts[i+1]，再次移动 l 和 r 找出满足区间的最小点和最大点，因为数组是递增的，l 和 r只能向右移动，使得问题简单很多。
利用归并排序合并时特点，每次合并的2个数组都是有序的
假设下图为归并排序某一次合并的状态。
在合并前我们利用两2个数组的有序性先求得满足区间的个数。


归并排序：https://www.runoob.com/w3cnote/merge-sort.html

方法一：前缀和 + 归并排序
先写一个归并排序，在每次合并前先求满足区间的个数
将代码中【统计代码】去掉，即为归并排序

public int countRangeSum(int[] nums, int lower, int upper) {
    // 前缀和数组
    long[] preSums = new long[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        preSums[i + 1] = preSums[i] + nums[i];
    }

    return mergeSort(preSums, 0, preSums.length - 1, lower, upper);
}


 // 归并排序

public int mergeSort(long[] preSums, int left, int right, int lower, int upper) {
    if (left == right) {
        return 0;
    }
    // 分解
    int mid = (left + right) / 2;
    int retL = mergeSort(preSums, left, mid, lower, upper);
    int retR = mergeSort(preSums, mid + 1, right, lower, upper);

    int ret = retL + retR;

    // 在合并数组前统计2个升序数组满足的角标对
    // 【统计】开始
    int i = left;
    int l = mid + 1;
    int r = mid + 1;
    while (i <= mid) {
        // 移动左指针找出满足区间的最小角标
        while (l <= right && preSums[l] - preSums[i] < lower) {
            l++;
        }
        // 移动右指针找出满足区间的最大角标 + 1
        while (r <= right && preSums[r] - preSums[i] <= upper) {
            r++;
        }
        ret += (r - l);
        i++;
    }
    // 【统计】结束

    // 合并
    merge(preSums, left, mid, right);

    return ret;
}

    public void merge(long[] arr, int left, int mid, int right) {
        long[] temp = new long[right - left + 1];

        int i = 0;

        int p1 = left;
        int p2 = mid + 1;

        // 比较两个数组，依次将小的元素放入temp，直到遍历完其中一个数组
        while (p1 <= mid && p2 <= right) {
            temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        // 将未遍历完的数组放入temp
        while (p1 <= mid) {
            temp[i++] = arr[p1++];
        }
        while (p2 <= right) {
            temp[i++] = arr[p2++];
        }

        // 改变原数组
        for (int j = 0; j < temp.length; j++) {
            arr[left + j] = temp[j];
        }
    }

        执行结果：

        时间复杂度： 和归并排序一致 O(NlogN)
        空间复杂度： 和归并排序一致 O(N)

        附暴力法：
public int countRangeSum1(int[] nums, int lower, int upper) {
        long[] temp = new long[nums.length];
        for (int i = 0; i < nums.length; i++) {
        temp[i] =  nums[i] + 0L;
        }

        int ans = 0;
        for (int i = 0; i < temp.length; i++) {
        long c = 0;
        for (int j = i; j < temp.length; j++) {
        c += temp[j];
        if (c >= lower && c <= upper) {
        ans++;
        }
        }
        }
        return ans;
        }

        文章已被收录至官方知识档案
        算法技能树leetcode-排序算法327-区间和的个数43774 人正在系统学习中
        ————————————————
        版权声明：本文为CSDN博主「喜欢下雨所以爱上雷震子」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
        原文链接：https://blog.csdn.net/qq_27007509/article/details/109559053
 */
/*
参考的网上的思路。

首先得到presums，可用数组也可不用。

对于每个presums[i]，我们要得到所有的nums[j]使得lower<=presums[i] - presums[j]<=upper，即

presums[i] >= presumes[j] + lower //我们要找到所有presums[i] - lower >= presums[j]的presums[j]，当j小于一定值后所有的presums[j'都满足，所以取upper。
presums[i] <= presums[j] + upper //我们要找到所有presums[i] - upper <= presums[j]的presums[j]，当j大于一定值后所有的presums[j]都满足，所以取lower。



class Solution {
public:

int countRangeSum(vector<int> &nums, int lower, int upper) {
    int n = nums.size();
    multiset<long long> ms;
    long long presums = 0;
    int result = 0;
    ms.insert(0);

    for (int i = 0; i < n; ++i) {
        presums += nums[i];
        result += distance(ms.lower_bound(presums - upper), ms.upper_bound(presums - lower));
        ms.insert(presums);
    }

    return result;
}
}
————————————————
        版权声明：本文为CSDN博主「纸上得来终觉浅 绝知此事要躬行」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
        原文链接：https://blog.csdn.net/roufoo/article/details/106566963
 */

/*
LintCode-Logo
学习
刷题
题集
群组
内推
VIP
CAT
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
1293 · 区间和的个数
算法
困难
通过率
44%
题目
题解14
笔记22
讨论2
排名
记录
描述
给定一个整数数组nums，返回[lower，upper]范围内的区间和数量。
区间和S(i, j)被定义为索引i和j(i ≤ j)之间（包含i和j）的nums中所有元素的和。

北美在招WLB&高薪厂面经曝光

微信加sunny【jiuzhang1104】备注【在招】即可领取


暴力解法的时间复杂度为O(n^2)。给出的解法必须好于这个方法。

样例
样例 1:

输入：[-2, 5, -1],-2,2
输出：3
解释：三个区间分别是: [0,0], [2,2], [0,2] ，它们对应的区间和分别为: -2, -1, 2。
样例 2:

输入：[0,-3,-3,1,1,2],3,5
输出：2
解释：三个区间分别是: [3, 5], [4, 5] ，它们对应的区间和分别为: 4, 3。
标签
企业
谷歌
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
121/402
已开启智能提示
发起考试
45 分 00 秒
1234567891011
}
控制台
历史提交
您有321条未读消息，请及时查看

 */
